package Aufgabe1_gleichwertige_loesungen;

public class BuchLoesung {
    // Teilsumme.java
// Algorithmen und Datenstrukturen, Kapitel 2.1
// Autor: Prof. Solymosi, (c) 2000: APSIS GmbH
// Datum: 14. April 2000

	int maxTeilsumme3 (final int[] folge) {
		int maxSumme = Integer.MIN_VALUE;
		for (int von = 0; von < folge.length; von++)
			for (int bis = von; bis < folge.length; bis++) { // Summe bilden
				int summe = 0;
				for (int i = von; i <= bis; i++)
					summe += folge[i];
					maxSumme = Math.max(summe, maxSumme); // Summe überprüfen, ob größer
			};
		return maxSumme;
	}
	int maxTeilsumme2(final int[] folge) {
		int[][] s = new int [folge.length] [folge.length];
		// Tabelle für Teilsummen: für i ( j gilt
		// s[i][j] == Teilsumme i bis j == folge[i]+folge[i+1]+...+folge[j]
		for (int i = 0; i < folge.length; i++)
			for (int j = 0; j < folge.length; j++)
				s[i][j] = 0;
		int max = Integer.MIN_VALUE;
		s[0][0] = folge[0]; // Teilsumme 0 bis 0
		for (int bis = 1; bis < folge.length; bis++)
			s[0][bis] = s [0][bis - 1] + folge[bis];
		// Teilsummen 0 bis 1, ..., 0 bis n-1
		// auf die vorherige Teilsumme wird das nächste Element addiert
		for (int von = 1; von < folge.length; von++)
			for (int bis = von; bis < folge.length; bis++)
				s[von][bis] = s[von - 1][bis] - folge[von - 1];
		// Teilsumme fängt um ein Element nach rechts an: um dieses Element kleiner
		// Tabelle s wurde gefüllt; jetzt kann das maximale Element gesucht werden:
		for (int von = 0; von < folge.length; von++)
			for (int bis = 0; bis < folge.length; bis++)
				max = Math.max(max, s[von][bis]); // Summe überprüfen, ob größer
	if (folge.length == 0)
		return 0; // die Summe der leeren Teilfolge ist 0
	else
		return max;
	}
	private int rechtesRandMax(final int[] folge, int links, int rechts) {
		// requires 0 <= links <= rechts < folge.length
		// berechnet rechtes Randmaximum in folge zwischen links und rechts
		int bisherMax = Integer.MIN_VALUE;
		int bisherSum = 0;
		for (int i = rechts; i >= links; i--) {
			bisherSum += folge[i];
			bisherMax = Math.max(bisherMax, bisherSum);
		};
		return bisherMax;
	}
	private int linkesRandMax(final int[] folge, int links, int rechts) {
		// requires 0 <= links <= rechts < folge.length
		// berechnet linkes Randmaximum in folge zwischen links und rechts
		int bisherMax = Integer.MIN_VALUE;
		int bisherSum = 0;
		for (int i = links; i <= rechts; i++) {
			bisherSum += folge[i];
			bisherMax = Math.max(bisherMax, bisherSum);
		};
		return bisherMax;
	}
	private int maxTeilsummeRekursiv(final int[]folge,int links,int rechts) {
		// requires 0 <= links <= rechts < folge.length
		// berechnet maximale Teilsumme in folge zwischen links und rechts
		if (links == rechts) // nur ein Element
			return Math.max(0, folge[links]);
		else {
			final int mitte = (rechts + links)/2;
			final int maxLinks = maxTeilsummeRekursiv(folge, links, mitte);
			final int maxRechts = maxTeilsummeRekursiv(folge, mitte+1, rechts);
			final int rechtesMax = rechtesRandMax(folge, links, mitte);
				// linke Hälfte
			final int linkesMax = linkesRandMax(folge, mitte+1, rechts);
				// rechte Hälfte
			return Math.max(maxRechts, Math.max(maxLinks, rechtesMax+linkesMax));
		}
	}
	public int maxTeilsummeRekursiv(final int[] folge) {
		// berechnet maximale Teilsumme von folge
		return maxTeilsummeRekursiv(folge, 0, folge.length-1);
	}
	int maxTeilsumme1(final int[] folge) {
		int bisherMax = 0;
		int randMax = 0;
		for (int i = 0; i < folge.length; i++) {
			randMax = Math.max(0, randMax + folge[i]);
			bisherMax = Math.max(bisherMax, randMax);
		};
		return bisherMax;
	}
}
